package leetcode.code6077;

import java.util.Stack;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution3 implements IDebug {

	class MaxStack {
		int[] stack;
		int len;
		int p;

		public MaxStack(int len) {
			this.stack = new int[len];
			this.len = len;
			this.p = 0;
		}

		public void add(int val) {
			this.stack[p++] = val;
		}

		public int peek() {
			return this.stack[this.p - 1];
		}

		public int pop() {
			return this.stack[--this.p];
		}

		public boolean isEmpty() {
			return this.p == 0;
		}
	}

	int mod = (int) 1e9 + 7;

	public int totalStrength(int[] strength) {
		int len = strength.length;
		long preSum = 0;
		long[] sumSum = new long[len + 2];
		for (int i = 2; i < len + 2; i++) {
			preSum += strength[i - 2];
			sumSum[i] = (sumSum[i - 1] + preSum) % mod;
		}
		Stack<Integer> stack = new Stack<>();
		long ans = 0;
		for (int i = 0; i < len; i++) {
			while (!stack.isEmpty() && strength[stack.peek()] >= strength[i]) {
				int min = stack.pop();
				int l = stack.isEmpty() ? -1 : stack.peek();
				ans += magicSum(strength, sumSum, l + 1, min, i - 1);
				ans %= mod;
			}
			stack.add(i);
		}
		while (!stack.isEmpty()) {
			int min = stack.pop();
			int l = stack.isEmpty() ? -1 : stack.peek();
			ans += magicSum(strength, sumSum, l + 1, min, len - 1);
			ans %= mod;
		}
		return (int) ans;
	}

	public long magicSum(int[] arr, long[] sumSum, int L, int M, int R) {
		long rightSum = 1L * (M - L + 1) * (sumSum[R + 2] + mod - sumSum[M + 1]) % mod;
		long leftSum = 1L * (R - M + 1) * (sumSum[M + 1] + mod - sumSum[L]) % mod;
		return 1L * arr[M] * (rightSum + mod - leftSum) % mod;
	}

	@Override
	public void debug4() {
		H.compare(44, this.totalStrength(H.str2array3("[1,3,1,2]")));
		H.compare(822, this.totalStrength(H.str2array3("[1,3,2,4,5,2,4,2,1]")));
		this.totalStrength(H.str2array3("[1,3,2,4,5,2,4,2,1]"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
